Computerized devices control almost every aspect of our life—from writing documents to controlling traffic lights. However, computerized devices are bug-prone, and thus require a testing phase in which the bugs should be discovered. The testing phase is considered one of the most difficult tasks in designing a computerized device. The cost of not discovering a bug may be enormous, as the consequences of the bug may be disastrous. For example, a bug may cause the injury of a person relying on the designated behavior of the computerized device. Additionally, a bug in hardware or firmware may be expensive to fix, as patching it requires call-back of the computerized device. Hence, many developers of computerized devices invest a substantial portion of the development cycle to discover erroneous behaviors of the computerized device.
During the testing phase a System Under Test (SUT) is being tested. The SUT may be, for example, a computer program, a hardware device, a firmware, an embedded device, a component thereof, or the like. Testing may be performed using a test suite that comprises tests. The test suite may be reused to revalidate that the SUT exhibits a desired functionality with respect to the tests of the test suite. For example, the test suite may be reused to check that SUT works properly after a bug is fixed. The test suite may be used to check that the bug is indeed fixed (with respect to a test that previously induced the erroneous behavior). Additionally or alternatively, the test suite may be used to check that no new bugs were introduced (with respect to other tests of the tests suite that should not be affected by the bug fix).
Test selection is a technique for reducing the testing effort by selecting a subset of the existing tests to run, while preserving a level of confidence in the coverage of the selected tests (see Graves, T. L., Harrold, M., Kim, J.-M., Porter, A., Rothermel, G. An empirical study of regression test selection techniques. ACM Trans. Softw. Eng. Methodol., 184-208 (2001)). The most common criterion for test selection is code coverage, i.e., select a subset of the tests that cover the same code as the original set of tests, or cover code that has recently changed. Other possible criteria for test selection are counts of execution, data values, def-use of variables, and execution time.